#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stack>

using namespace std;

/* 
 * 产生式 A->B B->i|ε
 */
struct production
{
    char left;
    string right;
};

struct grammer
{
    string t_;
    string n_;
    vector<production> p_;
} grammer;

map<char, set<char>> first;
map<char, set<char>> follow;

stack<char> ST;

string str;

string M[50][50];

int isT(char ch)
{
    string::size_type n;
    n = grammer.t_.find(ch);
    if (n != string::npos)
        return n;
    else
        return false;
}

int isN(char ch)
{
    string::size_type n;
    n = grammer.n_.find(ch);
    if (n != string::npos)
        return n;
    else
        return false;
}

void getFirst() {
    for (int i = 0; i < grammer.t_.size(); ++i) {
        char x = grammer.t_[i];
        set<char> tmp;
        tmp.insert(x);
        first[x] = tmp;
    }

    bool change = true;
    while (change) {
        change = false;
        for (int i = 0; i < grammer.p_.size(); ++i) {
            production &p = grammer.p_[i];
            char x = p.left;
            set<char> &FX = first[x];
            if (isT(p.right[0]) || p.right[0]=='&') {
                auto it = FX.find(p.right[0]);
                if (it == FX.end()) {
                    change = true;
                    FX.insert(p.right[0]);
                }
            } else {
                bool next = true;
                int idx = 0;
                while (next && idx < p.right.size()) {
                    next = false;
                    char y = p.right[idx];
                    set<char> &FY = first[y];
                    for (auto it = FY.begin(); it != FY.end(); ++it) {
                        if (*it != '&') {
                            auto itt = FX.find(*it);
                            if (itt == FX.end()) {
                                change = true;
                                FX.insert(*it);
                            }
                        }
                    }
                    auto it = FY.find('&');
                    if (it != FY.end()) {
                        next = true;
                        idx = idx + 1;
                    }
                }
            }
        }
    }

    cout << "first" << endl;
    for (int i = 0; i < grammer.n_.size(); ++i) {
        char x = grammer.n_[i];
        cout << x << ":";
        for (auto it = first[x].begin(); it != first[x].end(); ++it) {
            cout << *it << " ";
        }
    }
    cout << endl;
}

void getFirstByal(string &al, set<char> &FS) {
    bool next = true;
    int idx = 0;
    while (next && idx < al.size()) {
        next = false;
        if (isT(al[idx]) || al[idx]=='&') {
            auto itt = FS.find(al[idx]);
            if (itt == FS.end()) {
                FS.insert(al[idx]);
            }
        } else {
            char b = al[idx];
            set<char> &FB = first[b];
            for(auto it = first[b].begin(); it != first[b].end(); ++it) {
                if (*it == '&') {
                    next = true;
                    continue;
                }
                auto itt = FS.find(*it);
                if (itt == FS.end()) {
                    FS.insert(*it);
                }
            }
        }
        idx = idx + 1;
    }
    if (next) {
        FS.insert('&');
    }
}

void getFollow() {
    for (int i = 0; i < grammer.n_.size(); ++i) {
        char b = grammer.n_[i];
        follow[b] = set<char>();
    }

    char s = grammer.n_[0];
    follow[s].insert('$');

    bool change = true;
    while (change) {
        change = false;
        for (int i = 0; i < grammer.p_.size(); ++i) {
            production &p = grammer.p_[i];
            for (int j = 0; j < p.right.size(); ++j) {
                char b= p.right[j];
                if (isN(b)) {
                    set<char> &FB = follow[b];
                    set<char> FS;
                    string al(p.right.begin()+j+1, p.right.end());
                    getFirstByal(al, FS);

                    for (auto it = FS.begin(); it != FS.end(); ++it) {
                        if ('&' == *it) {
                            continue;
                        }
                        auto itt = FB.find(*it);
                        if (itt == FB.end()) {
                            change = true;
                            FB.insert(*it);
                        }
                    }

                    auto itt = FS.find('&');
                    if (itt != FS.end() || (j+1)>=p.right.size()) {
                        char a = p.left;
                        for (auto it = follow[a].begin(); it != follow[a].end(); ++it) {
                            auto itt = FB.find(*it);
                            if (itt == FB.end()) {
                                change = true;
                                FB.insert(*it);
                            }
                        }
                    }
                }
            }
        }
    }

    cout << "follow" << endl;
    for (int i = 0; i < grammer.n_.size(); ++i) {
        char x = grammer.n_[i];
        cout << x << ":";
        for (auto it = follow[x].begin(); it != follow[x].end(); ++it) {
            cout << *it <<" ";
        }
        cout << endl;
    }
}

void insert_forecast(char A, char a, production &p) {
    int i = isN(A) - 1;
    int j = isT(a) - 1;
    M[i][j].push_back(p.left);
    M[i][j].push_back('-');
    M[i][j].push_back('>');
    for (auto it = p.right.begin(); it != p.right.end(); ++it) {
        M[i][j].push_back(*it);
    }
}

void getAnaly(char A, char a, string &s) {
    int i = isN(A) - 1;
    int j = isT(a) - 1;
    s.assign(M[i][j].begin(), M[i][j].end());
}

void productAnalyseTable() {
    for (int i = 0; i < grammer.p_.size(); ++i) {
        production &p = grammer.p_[i];
        set<char> FS;
        getFirstByal(p.right, FS);
        for (auto it = FS.begin(); it != FS.end(); ++it) {
            insert_forecast(p.left, *it, p);
        }

        auto itt = FS.find('&');
        if (itt != FS.end()) {
            for (auto it = follow[p.left].begin(); it != follow[p.left].end(); ++it) {
                insert_forecast(p.left, *it, p);
            }
        }
    }
}

void process() {
    int ip = 0;
    char X, a;
    do {
        X = ST.top();
        a = str[ip];
        if (isT(X)) {
            if (X == a) {
                ST.pop();
                ip = ip + 1;
            } else {
                cout << "error" << endl;
            }
        } else {
            string s;
            getAnaly(X, a, s);
            if (!s.empty()) {
                ST.pop();
                for (int i = s.size() - 1; i >=3; --i) {
                    if (s[i] != '&') {
                        ST.push(s[i]);
                    }
                }

                for (int i = 0; i < s.size(); ++i) {
                    cout << s[i];
                }
                cout << endl;
            } else {
                cout << "error" << endl;
            }
        } 
    } while (X!='$');
}

int main() {}